/* 用邻接表存储无向图G，具有n个顶点，其值分别为从1到n，试设计一个算法，判断该无向图G是否是一棵树。若是树，返回1；否则返回0.（一个无向图G是一棵树的条件是：G必须是无回路的连通图或者是有n-1条边的连通图）
输入：
首先输入无向图的顶点个数n和边的数目m
输入n个顶点，顶点之间用空格分开
输入m条边

输出：
1或者0

输入：
5 4
1 2 3 4 5
1 2
1 4
2 3
4 5
输出：
1 */

#include <iostream>
#include <queue>
using namespace std;
#define MVNum 1000//最大顶点数
int visited[MVNum]={0};//判别顶点是否被访问过
typedef struct ArcNode//边结点
{
    int adjvex; //该边所指向的顶点的位置
    struct ArcNode *nextarc; //指向下一条边的指针
    //OtheInfo info;//边相关的信息（如权值）
}ArcNode;

typedef struct VNode//顶点信息
{ 
    int data;
    ArcNode *firstarc; //指向第一条依附该顶点的边的指针
}VNode, AdjList[MVNum];//AdjList表示邻接表类型为VNode型数组

typedef struct//邻接表
{
    AdjList adjlist;
    int vexnum, arcnum; //图的当前顶点数和边数
}ALG;//邻接表

int LocateVex(ALG G, int v)//邻接表G中v的位置
{
    for(int i=1; i<=G.vexnum; i++)
    {
        if(G.adjlist[i].data == v)
           return i;
    }
    return -1;
}

void CreateUDG(ALG &G)//邻接表表示法，创建 无向图G
{
    int i, k, temp;
    cin >> G.vexnum >> G.arcnum;//输入图总顶点数和总边数
    for (i = 1; i <= G.vexnum; i++) // 输入各点，构建 邻接表头结点表,从1开始编号
    {
        cin >> temp;
        G.adjlist[i].data = temp;
        G.adjlist[i].firstarc = NULL; //指向第一条依附该顶点的边的指针,初始化为NULL
    }
    for (k = 0; k < G.arcnum; k++) // 输入各边，构建邻接表
    {
        int v1, v2;
        //char ch;
        //cin >> v1 >> ch >> v2; // 输入一条边的两个顶点
        scanf("%d%d",&v1,&v2);
        int i, j;
        i = LocateVex(G, v1);//确定v1和v2在G中位置i和j，即顶点在G.adjlist中的序号
        j = LocateVex(G, v2);
        ArcNode *p1,*p2;
        p1=new ArcNode;//生成一个新的边结点
        p1->adjvex = j;//该边所指向的顶点的位置为j，即该边的邻接点序号为j
        p1->nextarc = G.adjlist[i].firstarc;
        G.adjlist[i].firstarc = p1;//头插法，把新的边结点插入插入顶点Vi的 邻接边表 的头部
        p2=new ArcNode;//生成一个新的边结点
        p2->adjvex=i;//该边所指向的顶点的位置为i，即该边的邻接点序号为i
        p2->nextarc = G.adjlist[j].firstarc;
        G.adjlist[j].firstarc = p2;//头插法，把新的边结点插入插入顶点Vj的 邻接边表 的头部
    }
}

int vsum=0;//顶点个数
int esum=0;//边个数
int DFSAL(ALG G,int v)//深度优先遍历 邻接表 储存的图，从第v个顶点开始
{
  //  cout << v;//输出被访问顶点的编号（位置）
    visited[v] = 1;//标记被访问的点
    vsum++;//访问一个顶点就加一次顶点数
    ArcNode *p;
    p = G.adjlist[v].firstarc;//p为第v个顶点的第一条邻接边
    while(p!=NULL)
    {
        esum++;//访问一条边就加一次边数
        if(visited[LocateVex(G, p->adjvex)]==0)//p->adjvex为第v个顶点的第一条邻接边指向的顶点，即第v个顶点相邻顶点的位置。没有被访问
        {
           DFSAL(G, LocateVex(G, p->adjvex));//递归遍历
        }
        p = p->nextarc;//p移到下一个边结点
    }
    if(vsum==G.vexnum&&esum==2*(G.vexnum-1))
        return 1;
    else
        return 0;
}


int main()
{
    ALG G;
    int i;
    CreateUDG(G);
    i = DFSAL(G, 1);
    if(i==1)
        cout << '1';
    else
        cout << '0';
    return 0;
}